package bTree.LeetCode;

import javax.swing.tree.TreeNode;

public class 二叉树中的最大路径和 {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (null==root)return 0;
        int left=dfs(root.left);
        int right=dfs(root.right);
        //先考虑单个节点路径
        max=Math.max(max,root.val);
        //考虑左右组合的路径
        int path=root.val;
        if (left>=0)path+=left;
        if (right>=0)path+=right;
        max=Math.max(max,path);
        //返回节点带上大于0且比较大的子树
        if (left>0&&left>=right)return root.val+left;
        if (right>0&&left<=right)return root.val+right;
        return root.val;
    }
}